﻿/*
 * 名称：程序设计语言-编译原理算法LL（1）分析主程序
 * 制作者：WT
 * 创建时间：2012-9
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace CompilerDLL.SyntaxAnalysis.Top_Down_Analysis
{
    /// <summary>
    /// LL（1）分析相关算法类
    /// </summary>
    public class LL1_Analysis:BaseSyntaxParse 
    {
        #region 构造方法
        public LL1_Analysis()
        {
            this.InitiateForecastTable();
        }
        #endregion 

        #region 私有方法

        #region 判断栈顶元素是否为终结符
        /// <summary>
        /// 判断栈顶元素是否为终结符
        /// </summary>
        /// <param name="topStackSymbol"></param>
        private bool IsTerminalSymbol(string topStackSymbol)
        {
            int symbolType = (int)this.hashSymbolType[topStackSymbol];

            if (symbolType == 1)
            {
                return true;
            }
            else
            {
                return false;
            }

        }
        #endregion

        #region 在当前分析操作步，按逆序得到产生式右部符号，并入符号操作栈stackProcSymbols
        /// <summary>
        /// 在当前分析操作步，按逆序得到产生式右部符号，并入符号操作栈stackProcSymbols
        /// </summary>
        /// <param name="m">产生式的MODEL</param>
        private void PushProductonBodySymbolsInverted(ModelProduction m)
        {
            //得到预测分析表中当前产生式的右部，并利用一个栈反向的排列
            Stack stackBodySymbolsInverted = new Stack();
            int bodyLength = m.Body.Count;
            for (int i = 0; i < bodyLength; i++)
            {
                stackBodySymbolsInverted.Push((string)m.Body[i]);
            }

            //将符号放入符号操作栈stackProcSymbols
            int stackLength = stackBodySymbolsInverted.Count;
            for (int i = 0; i < stackLength; i++)
            {
                string symbol = (string)stackBodySymbolsInverted.Pop();
                if (symbol != "ε")
                {
                    this.stackProcSymbols.Push(symbol);
                }
            }
        }
        #endregion

        #region 在当前分析操作步，通过堆栈stackSyntaxTreeNode，生成当前的语法树
        /// <summary>
        /// 在当前分析操作步，通过堆栈stackSyntaxTreeNode，生成当前的语法树
        /// </summary>
        /// <param name="m">生成子节点所依赖的产生式</param>
        /// <param name="intCurrentStep">当前的执行步</param>
        private void GenerateCurrentSyntaxTree(
            ModelProduction m,
            int intCurrentStep)
        {
            
             //得到语法父节点
            SyntaxTreeNode syntaxTreeParentNode =
                (SyntaxTreeNode)this.stackSyntaxTreeNode.Pop();
            
            //得到预测分析表中当前产生式的右部，并利用一个栈反向的排列
            //同时该产生式的右部作为当前父节点的子节点
            Stack stackChildTreeNodeInverted = new Stack();
            int bodyLength = m.Body.Count;
            for (int i = 0; i < bodyLength; i++)
            {
                string symbol = (string)m.Body[i];

                SyntaxTreeNode syntaxTreeChildNode = new SyntaxTreeNode();
                syntaxTreeChildNode.NodeSymbol = symbol;
                syntaxTreeChildNode.ParentNode = syntaxTreeParentNode;
                syntaxTreeChildNode.Level =
                    syntaxTreeParentNode.Level + 1;
               
                //测试断点
                //if (syntaxTreeParentNode.Level > 4)
                //{
                //    int a = 0;
                //}
                syntaxTreeChildNode.IntCurrentStep = intCurrentStep;

                stackChildTreeNodeInverted.Push(syntaxTreeChildNode);
                syntaxTreeParentNode.ChildNodes.Add(syntaxTreeChildNode);
            }

           


            //将符号放入符号操作栈stackProcSymbols
            int stackLength = stackChildTreeNodeInverted.Count;
            for (int i = 0; i < stackLength; i++)
            {
                //设置当前栈中节点的子节点的属性
                SyntaxTreeNode treeNode = (SyntaxTreeNode)stackChildTreeNodeInverted.Pop();
                if (treeNode.NodeSymbol != "ε")
                {
                    this.stackSyntaxTreeNode.Push(treeNode);
                }
               
                
             
              
            }
        }
        #endregion 

        #region 按书第4章（式）4.2的文法结构生成预测表
        /// <summary>
        /// 按书第4章（式）4.2的文法结构生成预测表，进行初始化
        /// E->TE'
        /// E'->+TE'|ε
        /// T->FT’
        /// T'->*FT'|ε
        /// F->(E)|i
        /// </summary>
        private void InitiateForecastTable()
        {

            //在以下代码中5是标志符的单词符号类型编号

            #region 初始化预测表
            ModelProduction m1 = new ModelProduction();
            m1.Head = "E";
            m1.Body.Add("T");
            m1.Body.Add("E'");
            this.hashForecastTable.Add("Ei", m1);

            ModelProduction m2 = new ModelProduction();
            m2.Head = "E";
            m2.Body.Add("T");
            m2.Body.Add("E'");
            this.hashForecastTable.Add("E(", m2);

            ModelProduction m3 = new ModelProduction();
            m3.Head = "E'";
            m3.Body.Add("+");
            m3.Body.Add("T");
            m3.Body.Add("E'");
            this.hashForecastTable.Add("E'+", m3);

            ModelProduction m4 = new ModelProduction();
            m4.Head = "E'";
            m4.Body.Add("ε");
            this.hashForecastTable.Add("E')", m4);

            ModelProduction m5 = new ModelProduction();
            m5.Head = "E'";
            m5.Body.Add("ε");
            this.hashForecastTable.Add("E'#", m5);

            ModelProduction m6 = new ModelProduction();
            m6.Head = "T";
            m6.Body.Add("F");
            m6.Body.Add("T'");
            this.hashForecastTable.Add("Ti", m6);

            ModelProduction m7 = new ModelProduction();
            m7.Head = "T";
            m7.Body.Add("F");
            m7.Body.Add("T'");
            this.hashForecastTable.Add("T(", m7);

            ModelProduction m8 = new ModelProduction();
            m8.Head = "T'";
            m8.Body.Add("ε");
            this.hashForecastTable.Add("T'+", m8);

            ModelProduction m9 = new ModelProduction();
            m9.Head = "T'";
            m9.Body.Add("*");
            m9.Body.Add("F");
            m9.Body.Add("T'");
            this.hashForecastTable.Add("T'*", m9);

            ModelProduction m10 = new ModelProduction();
            m10.Head = "T'";
            m10.Body.Add("ε");
            this.hashForecastTable.Add("T')", m10);

            ModelProduction m11 = new ModelProduction();
            m11.Head = "T'";
            m11.Body.Add("ε");
            this.hashForecastTable.Add("T'#", m11);

            ModelProduction m12 = new ModelProduction();
            m12.Head = "F";
            m12.Body.Add("i");
            this.hashForecastTable.Add("Fi", m12);

            ModelProduction m13 = new ModelProduction();
            m13.Head = "F";
            m13.Body.Add("(E)");
            this.hashForecastTable.Add("F(", m13);
            #endregion

            #region 初始化符号类型
            this.hashSymbolType.Add("E", 0);
            this.hashSymbolType.Add("E'", 0);
            this.hashSymbolType.Add("T", 0);
            this.hashSymbolType.Add("T'", 0);
            this.hashSymbolType.Add("F", 0);
            this.hashSymbolType.Add("i", 1);
            this.hashSymbolType.Add("+", 1);
            this.hashSymbolType.Add("*", 1);
            this.hashSymbolType.Add("(", 1);
            this.hashSymbolType.Add(")", 1);

            #endregion
        }
        #endregion 

        #region 记录每一个分析步的状态


        /// <summary>
        /// 记录每一个分析步的当前状态
        /// </summary>
        /// <param name="inputIndex">当前的输入单词的指针</param>
        /// <param name="currentStep">当前的执行步</param>
        ///  <param name="modelCurrentProduction">当前步所用的产生式</param>
        /// <param name="currentSyntaxTreeNode">当前语法树状态</param>
        /// <returns>Model,保存每一次的当前分析状态</returns>
        private Model_LL1_StepStatus RecordCurrentForecastAnalysisSteps(
            int inputIndex,
            int currentStep,
            ModelProduction modelCurrentProduction,
            SyntaxTreeNode currentSyntaxTree)
        {
            Model_LL1_StepStatus model_LL1_StepStatus =
                new Model_LL1_StepStatus();
            #region (1).记录当前的执行步数。
            //(1).记录当前的执行步数。
            model_LL1_StepStatus.IntStep = currentStep;
            #endregion 

            #region (2)记录当前的单词符号串
            for (int i=inputIndex;i<this.arrayTokens.Count;i++)
            {
                 LexicalAnalysis.ModelTokenType modelCurrentToken=
                     (LexicalAnalysis.ModelTokenType)this.arrayTokens[i];
                 model_LL1_StepStatus.StrCurrentTokens += modelCurrentToken.Lexem;

            }
            #endregion

            #region (3).当前步的产生式
            if (modelCurrentProduction == null)
            {
                model_LL1_StepStatus.StrCurrentProduction = "";
            }
            else
            {
                model_LL1_StepStatus.StrCurrentProduction +=
                    modelCurrentProduction.Head;
                model_LL1_StepStatus.StrCurrentProduction +=
                    "->";
                for (int i = 0; i < modelCurrentProduction.Body.Count; i++)
                {
                    model_LL1_StepStatus.StrCurrentProduction +=
                        (string)modelCurrentProduction.Body[i];

                }

            }
            #endregion 

            #region (4).记录当前的栈状态
            //记录当前的栈状态
            Stack stackCurrent = (Stack)this.stackProcSymbols.Clone();
            int stackLength = stackCurrent.Count;
            for (int i = 0; i < stackLength; i++)
            {
                model_LL1_StepStatus.StrStackProcSymbols =
                    stackCurrent.Pop().ToString() + model_LL1_StepStatus.StrStackProcSymbols;
            }
            #endregion 


            #region (5).当前语法树状态
            if (currentSyntaxTree != null)
            {
                model_LL1_StepStatus.Current_Syntax_Tree = (SyntaxTreeNode)currentSyntaxTree.Clone();
            }
          
            #endregion 
            string strOutput =
                currentStep.ToString()
                +"    "+ model_LL1_StepStatus.StrStackProcSymbols
                +"    " + model_LL1_StepStatus.StrCurrentTokens
                +"    " + model_LL1_StepStatus.StrCurrentProduction;

            //Console.WriteLine(strOutput);
            return model_LL1_StepStatus;
            
        }
        #endregion

        #endregion

        #region 公用方法

        #region LL（1）预测分析主程序，重写父类
        /// <summary>
        /// 自上而下分析LL（1）的主程序，输入为源代码的单词串，基于预测分析表，返回预测分析的分步结果
        /// </summary>
        /// <param name="arrayTokens">ArrayList，源代码输入串</param>
        /// <returns>ArrayList,LL（1）语法分析的中间结果，其中的元素为Model_LL1_StepStatus</returns>
        public override ArrayList Syntax_Parse_Main(
            ArrayList arrayTokens,
            string strPara)
        {
            this.ModifyTheInputTokens(arrayTokens);

            //当前的执行步，从0开始
            int intCurrentStep = 0;

            //记录当前执行状态
            Model_LL1_StepStatus model_LL1_StepStatus;

            //初始化符号栈
            this.stackProcSymbols.Push("#");
            this.stackProcSymbols.Push("E");

            //初始化语法树根节点
            SyntaxTreeNode syntaxTreeRootNode = new SyntaxTreeNode();
            syntaxTreeRootNode.Level = 0;
            syntaxTreeRootNode.ParentNode = null;
            syntaxTreeRootNode.NodeSymbol = "E";
            syntaxTreeRootNode.IntCurrentStep = 0;
            stackSyntaxTreeNode.Push(syntaxTreeRootNode);

            //flag为false时退出循环
            bool flag = true;

            //标志当前正在解析的单词
            int intInputIndex = 0;

            //当前正在解析的单词的Model对象
            LexicalAnalysis.ModelTokenType mCurrentToken;


            //得到的栈号栈的栈项符号
            string topStackSymbol = "";

            //当前步时，将会在预测分析表中用到的产生式
            ModelProduction modelCurrentProduction;

            //记录下第0步的状态
            model_LL1_StepStatus =
                new Model_LL1_StepStatus();

            model_LL1_StepStatus = this.RecordCurrentForecastAnalysisSteps(
                intInputIndex,
                intCurrentStep,
                null,
                syntaxTreeRootNode);



            this.ArraySyntaxAnalysisSteps.Add(model_LL1_StepStatus);

            while (flag)
            {
                //记录当前的执行步数
                intCurrentStep++;

                //得到栈顶符号
                topStackSymbol =
                    this.stackProcSymbols.Pop().ToString();

                //得到当前指针所指示的单词符号
                mCurrentToken =
                    (LexicalAnalysis.ModelTokenType)arrayTokens[intInputIndex];

                #region (1).如果栈项符号已经为“#”，且当前单词符号也为“#”，则分析结束
                //如果栈项符号已经为“#”，且当前单词符号也为“#”，则分析结束
                if ((topStackSymbol == "#") && (mCurrentToken.Lexem == "#"))
                {
                    flag = false;
                    break;
                }
                #endregion

                #region (2).否则，继续执行
                else
                {
                    #region (2.1)如果栈顶元素是终结符，则提取下一个单词
                    if (this.IsTerminalSymbol(topStackSymbol))
                    {
                        intInputIndex++;
                        this.stackSyntaxTreeNode.Pop();

                        #region (3).记录每一步的分析状态

                        //记录堆栈状态
                        model_LL1_StepStatus =
                        new Model_LL1_StepStatus();

                        model_LL1_StepStatus = this.RecordCurrentForecastAnalysisSteps(
                            intInputIndex,
                            intCurrentStep,
                            null,
                            syntaxTreeRootNode);
                        this.ArraySyntaxAnalysisSteps.Add(model_LL1_StepStatus);

                       
                        #endregion
                    }
                    #endregion

                    #region (2.2).否则，提取预测表中进一步的产生式，继续分析
                    else
                    {
                        //如果是标识符时，统一按i来索引
                        if ((mCurrentToken.TokenType == 5) || (mCurrentToken.TokenType == 1))
                        {
                            modelCurrentProduction = (ModelProduction)this.hashForecastTable[topStackSymbol + "i"];
                            this.PushProductonBodySymbolsInverted(modelCurrentProduction);
                            this.GenerateCurrentSyntaxTree(modelCurrentProduction,intCurrentStep);

                            #region 记录每一步的分析状态

                            //记录堆栈状态
                            model_LL1_StepStatus =
                            new Model_LL1_StepStatus();

                            model_LL1_StepStatus = this.RecordCurrentForecastAnalysisSteps(
                                intInputIndex,
                                intCurrentStep,
                                modelCurrentProduction,
                                syntaxTreeRootNode);
                            this.ArraySyntaxAnalysisSteps.Add(model_LL1_StepStatus);

                           
                            #endregion
                        }
                        else
                        {
                            modelCurrentProduction = (ModelProduction)this.hashForecastTable[topStackSymbol + mCurrentToken.Lexem];
                            this.PushProductonBodySymbolsInverted(modelCurrentProduction);
                            this.GenerateCurrentSyntaxTree(modelCurrentProduction, intCurrentStep);

                            #region 记录每一步的分析状态

                            //记录堆栈状态
                            model_LL1_StepStatus =
                            new Model_LL1_StepStatus();

                            model_LL1_StepStatus = this.RecordCurrentForecastAnalysisSteps(
                                intInputIndex,
                                intCurrentStep,
                                modelCurrentProduction,
                                syntaxTreeRootNode);
                            this.ArraySyntaxAnalysisSteps.Add(model_LL1_StepStatus);

                           
                            #endregion
                        }
                    }
                    #endregion
                }
                #endregion

               
            }

            //赋值给语法树节点
            this.syntaxTree = syntaxTreeRootNode;

            return this.ArraySyntaxAnalysisSteps;

            
        }
        #endregion 

        #region 生成预测分析表
        /// <summary>
        /// 根据输入的产生式的列表，构造出预测分析表
        /// </summary>
        /// <param name="arrayProductions">产生式的列表，其中的元素的类型为ModelProduction</param>
        /// <returns>预测分析表的HashTable存储结构，其中的元素的类型为ModelProduction</returns>
        public Hashtable GenerateForecastTable(ArrayList arrayProductions)
        {

            return null;
        }
        #endregion

        #endregion

    }
}
